/*
https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/solution/1080-gen-dao-xie-lu-jing-shang-de-bu-zu-9ve0o/
 */
public class Solution1080 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (root==null){
            return null;
        }
        if (root.left==null && root.right==null){
            return root.val<limit?null:root;
        }
        root.left=sufficientSubset(root.left,limit-root.val);
        root.right=sufficientSubset(root.right,limit-root.val);
        if (root.left==null && root.right==null){
            return null;
        }else {
            return root;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1080().sufficientSubset(new TreeNode(1,new TreeNode(2,new TreeNode(4,new TreeNode(8),new TreeNode(9)),new TreeNode(-99,new TreeNode(-99),new TreeNode(-99))),new TreeNode(3,new TreeNode(-99,new TreeNode(12),new TreeNode(13)),new TreeNode(7,new TreeNode(-99),new TreeNode(14)))),1).left.right);
    }
}
